package pers.lan.linkedlist;

/**
 * @author <p><a href="mailto:1728209643@qq.com">XiaoSan</a>
 * @date 2019/11/21 4:44 PM
 */
public class LC_147 {

    public static void main(String[] args) {
        ListNode head = ListNode.build(new int[]{-1, 5, 3, 4, 0});
        System.out.println(new LC_147().insertionSortList(head));
    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head.next;
        head.next = null;

        while (p != null) {
            ListNode q;
            if (head.val > p.val) {
                q = p.next;
                p.next = head;
                head = p;
                p = q;
            } else {
                q = head;
                loop:
                {
                    while (q.next != null) {
                        if (q.next.val > p.val) {
                            ListNode r = q.next;
                            q.next = p;
                            p = p.next;
                            q.next.next = r;
                            break loop;
                        }
                        q = q.next;
                    }
                    q.next = p;
                    p = p.next;
                    q.next.next = null;
                }
            }
        }

        return head;
    }
}
